package com.peng.leetcode.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * BuildTree
 *
 * @author: lupeng6
 * @create: 2021/1/4 15:04
 */
public class BuildTree {

    public static void main(String[] args) {
//        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        int[] postorder = {9, 15, 7, 20, 3};
//        TreeNode treeNode = new BuildTree().buildTree(preorder, inorder);
        TreeNode treeNode = new BuildTree().buildTree1(inorder, postorder);
        System.out.println(treeNode);
    }

    private Map<Integer, Integer> indexMap = new HashMap<>();
    private int[] preorder;

    private int[] postOrder;

    /**
     * 前序遍历 preorder = [3,9,20,15,7]
     * 中序遍历 inorder = [9,3,15,20,7]
     *
     * @author lupeng6
     * @date 2021/1/4 15:15
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        this.preorder = preorder;
        TreeNode treeNode = helper(0, preorder.length, 0, inorder.length);
        return treeNode;
    }

    public TreeNode helper(int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft >= preRight) {
            return null;
        }
        int rootIndex = preLeft;
        int rootVal = preorder[rootIndex];
        int inorderRootIndex = indexMap.get(rootVal);
        int leftTreeLength = inorderRootIndex - inLeft;
        TreeNode root = new TreeNode(rootVal);
        root.left = helper(preLeft + 1, preLeft + leftTreeLength + 1, inLeft, inorderRootIndex);
        root.right = helper(preLeft + leftTreeLength + 1, preRight, inorderRootIndex + 1, inRight);
        return root;
    }

    public TreeNode buildTree1(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        this.postOrder = postorder;
        TreeNode treeNode = helper1(0, inorder.length - 1, 0, postorder.length - 1);
        return treeNode;
    }

    public TreeNode helper1(int inorderLeft, int inorderRight, int postOrderLeft, int postOrderRight) {
        if (postOrderLeft > postOrderRight) {
            return null;
        }
        int rootIndex = postOrderRight;
        int rootVal = postOrder[rootIndex];
        int inorderRootIndex = indexMap.get(rootVal);
        int rightTreeNum = postOrderRight - inorderRootIndex + 1;

        TreeNode treeNode = new TreeNode(rootVal);
        treeNode.right = helper1(inorderRootIndex, inorderRight, postOrderRight - rightTreeNum, postOrderRight - 1);
        treeNode.left = helper1(inorderLeft, inorderRootIndex - 1, postOrderLeft + 1, postOrderRight - rightTreeNum);
        return treeNode;
    }

}
